{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Selling Pieces of Wood"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sellingWood"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #卖木头块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数&nbsp;<code>m</code> 和&nbsp;<code>n</code>&nbsp;，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组&nbsp;<code>prices</code>&nbsp;，其中&nbsp;<code>prices[i] = [h<sub>i</sub>, w<sub>i</sub>, price<sub>i</sub>]</code>&nbsp;表示你可以以&nbsp;<code>price<sub>i</sub></code>&nbsp;元的价格卖一块高为&nbsp;<code>h<sub>i</sub></code>&nbsp;宽为&nbsp;<code>w<sub>i</sub></code>&nbsp;的矩形木块。</p>\n",
    "\n",
    "<p>每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>沿垂直方向按高度 <strong>完全</strong> 切割木块，或</li>\n",
    "\t<li>沿水平方向按宽度 <strong>完全</strong> 切割木块</li>\n",
    "</ul>\n",
    "\n",
    "<p>在将一块木块切成若干小木块后，你可以根据 <code>prices</code>&nbsp;卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 <strong>不能</strong>&nbsp;旋转切好后木块的高和宽。</p>\n",
    "\n",
    "<p>请你返回切割一块大小为<em>&nbsp;</em><code>m x n</code><em> </em>的木块后，能得到的&nbsp;<strong>最多</strong>&nbsp;钱数。</p>\n",
    "\n",
    "<p>注意你可以切割木块任意次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/27/ex1.png\" style=\"width: 239px; height: 150px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]\n",
    "<b>输出：</b>19\n",
    "<b>解释：</b>上图展示了一个可行的方案。包括：\n",
    "- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。\n",
    "- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。\n",
    "- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。\n",
    "总共售出 14 + 3 + 2 = 19 元。\n",
    "19 元是最多能得到的钱数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/27/ex2new.png\" style=\"width: 250px; height: 175px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]\n",
    "<b>输出：</b>32\n",
    "<b>解释：</b>上图展示了一个可行的方案。包括：\n",
    "- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。\n",
    "- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。\n",
    "总共售出 30 + 2 = 32 元。\n",
    "32 元是最多能得到的钱数。\n",
    "注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>prices[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= h<sub>i</sub> &lt;= m</code></li>\n",
    "\t<li><code>1 &lt;= w<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>1 &lt;= price<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li>所有&nbsp;<code>(h<sub>i</sub>, w<sub>i</sub>)</code> <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [selling-pieces-of-wood](https://leetcode.cn/problems/selling-pieces-of-wood/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [selling-pieces-of-wood](https://leetcode.cn/problems/selling-pieces-of-wood/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n5\\n[[1,4,2],[2,2,7],[2,1,3]]', '4\\n6\\n[[3,2,10],[1,4,2],[4,1,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            f[h][w] = p\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(f[i][j],\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j // 2 + 1)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i // 2 + 1)), default=0))  # 水平切割\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        men = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for price in prices:\n",
    "            men[price[0]][price[1]] = price[2]\n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1): \n",
    "                for k in range(1, i):\n",
    "                    men[i][j] = max(men[i][j], men[k][j]+men[i-k][j])\n",
    "                for k in range(1, j):\n",
    "                    men[i][j] = max(men[i][j], men[i][k]+men[i][j-k])\n",
    "        \n",
    "        return men[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            f[h][w] = p\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(f[i][j],\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j // 2 + 1)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i // 2 + 1)), default=0))  # 水平切割\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # 初始化动态规划数组，默认为0\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        # 将给定的价格填入dp数组中相应的位置\n",
    "        for h, w, price in prices:\n",
    "            dp[h][w] = price\n",
    "        \n",
    "        # 动态规划计算最大价值\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                # 不仅考虑直接卖出去的价格，还要考虑横向和纵向切割的情况\n",
    "                for k in range(1, i // 2 + 1):  # 纵向切割木块，更新dp[i][j]\n",
    "                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])\n",
    "                for k in range(1, j // 2 + 1):  # 横向切割木块，更新dp[i][j]\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])\n",
    "        \n",
    "        # 返回最终的最大价值\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            f[h][w] = p\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(f[i][j],\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j // 2 + 1)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i // 2 + 1)), default=0))  # 水平切割\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "\n",
    "        f = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for xi,yi,pi in prices:\n",
    "            f[xi][yi] = pi\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                for k in range(1,i):\n",
    "                    f[i][j] = max(f[i][j],f[i-k][j]+f[k][j])\n",
    "                for k in range(1,j):\n",
    "                    f[i][j] = max(f[i][j],f[i][j-k]+f[i][k])\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "f[i][j] 表示高度为i,宽度为j的木块售卖能获得的最多收益\n",
    "状态转移，三种情况，直接售卖，垂直切割，水平切割，取最大\n",
    "f[i][j] = max(直接售卖，f[i][k] + f[i][j-k], f[k][j] + f[i-k][j])\n",
    "'''\n",
    "class Solution:\n",
    "    def sellingWood1(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        pr = {(h, w): p for h, w, p in prices}\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(pr.get((i, j), 0),\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i)), default=0))  # 水平切割\n",
    "        return f[m][n]\n",
    "        \n",
    "        \n",
    "    '''\n",
    "    优化两点，内层循环到一半即可；从小到大计算f，那么prices直接记录到f里不影响\n",
    "    '''\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            f[h][w] = p\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(f[i][j],\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j // 2 + 1)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i // 2 + 1)), default=0))  # 水平切割\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for h,w, p in prices:\n",
    "            f[h][w] = p \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                for x in range(1, i):\n",
    "                    f[i][j] = max(f[x][j]+f[i-x][j], f[i][j])\n",
    "                for y in range(1, j):\n",
    "                    f[i][j] = max(f[i][y]+f[i][j-y], f[i][j]) \n",
    "\n",
    "        return f[m][n] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for h, w, p in prices:\n",
    "            dp[h][w] = p \n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                for k in range(1, i):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-k][j] + dp[k][j])\n",
    "                for k in range(1, j):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][j-k] + dp[i][k]) \n",
    "        return dp[m][n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def sellingWood(self, m: int, n: int, ps: List[List[int]]) -> int:\n",
    "        # dp[i][j][k] 前i种划法 在高j 宽k的木块里的最大收益\n",
    "        num = len(ps)\n",
    "        m += 1\n",
    "        n += 1\n",
    "        ans = 0\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for x in ps:\n",
    "            dp[x[0]][x[1]] = x[2]\n",
    "        for j in range(1, m):\n",
    "            for k in range(1, n):\n",
    "                for i in range(j):\n",
    "                    dp[j][k] = max(dp[j][k], dp[j - i][k] + dp[i][k])\n",
    "                for i in range(k):\n",
    "                    dp[j][k] = max(dp[j][k], dp[j][k - i] + dp[j][i])\n",
    "                ans = max(ans, dp[j][k])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            f[h][w] = p\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(f[i][j], \\\n",
    "                        max((f[i][k] + f[i][j - k] for k in range(1, j // 2 + 1)), default=0),\\\n",
    "                        max((f[k][j] + f[i - k][j] for k in range(1, i // 2 + 1)), default=0))  \n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, price in prices:\n",
    "            dp[h][w] = price\n",
    "        for h in range(1, m + 1):\n",
    "            for w in range(1, n + 1):\n",
    "                price = dp[h][w]\n",
    "                for x in range(1, h):\n",
    "                    price = max(price, dp[x][w] + dp[h-x][w])\n",
    "                for x in range(1, w):\n",
    "                    price = max(price, dp[h][x] + dp[h][w-x])\n",
    "                dp[h][w] = price\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for h,w,p in prices:\n",
    "            if h <= m and w <= n:\n",
    "                # f[h][w] = max(f[h][w], p)\n",
    "                f[h][w] = p\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                for k in range(1,i):\n",
    "                    f[i][j] = max(f[i][j], f[k][j] + f[i-k][j])\n",
    "                for k in range(1,j):\n",
    "                    f[i][j] = max(f[i][j], f[i][k] + f[i][j-k])\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i][j] := maximum selling price from a pices of i * j\r\n",
    "# dp[i][0] = dp[0][j] = 0\r\n",
    "# dp[i][j] = max of\r\n",
    "#   dp[k][j] + dp[i - k][j] for 0 < k < i\r\n",
    "#   dp[i][k] + dp[i][j - k] for 0 < k < j\r\n",
    "#   price[i][j]\r\n",
    "class Solution:\r\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\r\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i, j, p in prices:\r\n",
    "            dp[i][j] = p\r\n",
    "        \r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                for k in range(1, i + 1):\r\n",
    "                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[k][j + 1] + dp[i - k + 1][j + 1])\r\n",
    "                for k in range(1, j + 1):\r\n",
    "                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][k] + dp[i + 1][j - k + 1])\r\n",
    "        \r\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            f[h][w] = p\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(f[i][j],\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j // 2 + 1)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i // 2 + 1)), default=0))  # 水平切割\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for h,w,p in prices:\n",
    "            if h <= m and w <= n:\n",
    "                # f[h][w] = max(f[h][w], p)\n",
    "                f[h][w] = p\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                for k in range(1, i//2+1):\n",
    "                    f[i][j] = max(f[i][j], f[k][j] + f[i-k][j])\n",
    "                for k in range(1, j//2+1):\n",
    "                    f[i][j] = max(f[i][j], f[i][k] + f[i][j-k])\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = 0\n",
    "        for x,y,w in prices:\n",
    "            dp[x][y] = w\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                for k in range(1,i):#横着切\n",
    "                    dp[i][j] = max(dp[i][j],dp[k][j]+dp[i-k][j])\n",
    "                for k in range(1,j):#竖着切\n",
    "                    dp[i][j] = max(dp[i][j],dp[i][k]+dp[i][j-k])\n",
    "        return dp[m][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # f[i][j]表示切割高i宽j的木块\n",
    "        # 一整块卖:f[i][j] = price[i][j]\n",
    "        # 横着劈:f[i][j] = max(f[k][j]+f[i-k][j]) for k in range(1,i)\n",
    "        # 竖着劈:f[i][j] = max(f[i][k]+f[i][j-k]) for k in range(1,j)\n",
    "        # 起点和终点,起点price[i][j],终点f[m][n]\n",
    "        f = [[0 for _ in range(n+1)]for _ in range(m+1)]\n",
    "        for hi,wi,pricei in prices:\n",
    "            f[hi][wi] = pricei\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                for k in range(1,i):\n",
    "                    f[i][j] = max(f[i][j],f[k][j]+f[i-k][j])\n",
    "                for k in range(1,j):\n",
    "                    f[i][j] = max(f[i][j],f[i][k]+f[i][j-k])\n",
    "        # for i in range(m+1):\n",
    "        #     for j in range(n+1):\n",
    "        #         for k in range(1,j):\n",
    "        #             f[i][j] = max(f[i][j],f[i][k]+f[i][j-k])\n",
    "        return f[m][n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i][j] := maximum selling price from a pices of i * j\r\n",
    "# dp[i][0] = dp[0][j] = 0\r\n",
    "# dp[i][j] = max of\r\n",
    "#   dp[k][j] + dp[i - k][j] for 0 < k < i\r\n",
    "#   dp[i][k] + dp[i][j - k] for 0 < k < j\r\n",
    "#   price[i][j]\r\n",
    "class Solution:\r\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\r\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i, j, p in prices:\r\n",
    "            dp[i][j] = p\r\n",
    "        \r\n",
    "        for i in range(1, m + 1):\r\n",
    "            for j in range(1, n + 1):\r\n",
    "                for k in range(1, i // 2 + 1):\r\n",
    "                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])\r\n",
    "                for k in range(1, j // 2 + 1):\r\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])\r\n",
    "\r\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # Create a memoization table to store the maximum money for each possible size\n",
    "        memo = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        # Fill the memoization table with the prices of the given shapes\n",
    "        for h, w, price in prices:\n",
    "            memo[h][w] = max(memo[h][w], price)\n",
    "\n",
    "        # Calculate the maximum money for each possible size by cutting the wood\n",
    "        for h in range(1, m + 1):\n",
    "            for w in range(1, n + 1):\n",
    "                # Try cutting the wood horizontally\n",
    "                for cut_h in range(1, h):\n",
    "                    memo[h][w] = max(memo[h][w], memo[cut_h][w] + memo[h - cut_h][w])\n",
    "\n",
    "                # Try cutting the wood vertically\n",
    "                for cut_w in range(1, w):\n",
    "                    memo[h][w] = max(memo[h][w], memo[h][cut_w] + memo[h][w - cut_w])\n",
    "\n",
    "        return memo[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            f[h][w] = p\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                for k in range(1, i // 2 + 1):\n",
    "                    f[i][j] = max(f[i][j], f[k][j] + f[i - k][j])\n",
    "                for k in range(1, j // 2 + 1):\n",
    "                    f[i][j] = max(f[i][j], f[i][k] + f[i][j - k])\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # 只能横切和竖切\n",
    "        # first method：dp\n",
    "        m, n = m + 1, n + 1\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for pri in prices:\n",
    "            dp[pri[0]][pri[1]] = pri[2]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                for k in range(1, i):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - k][j] + dp[k][j])\n",
    "                for k in range(1, j):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][j - k] + dp[i][k])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "        # second method: dfs\n",
    "\n",
    "        # def dfs()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # 只能横切和竖切\n",
    "        # first method：dp\n",
    "        m, n = m + 1, n + 1\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for pri in prices:\n",
    "            dp[pri[0]][pri[1]] = pri[2]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                for k in range(i):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - k][j] + dp[k][j])\n",
    "                for k in range(j):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][j - k] + dp[i][k])\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # 初始化 dp 二维数组，初始值都为0\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        \n",
    "        # 使用 prices 数组更新 dp 数组\n",
    "        for h, w, price in prices:\n",
    "            dp[h][w] = max(dp[h][w], price)\n",
    "        \n",
    "        # 动态规划过程\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                # 水平切割\n",
    "                for x in range(1, i):\n",
    "                    dp[i][j] = max(dp[i][j], dp[x][j] + dp[i-x][j])\n",
    "                \n",
    "                # 垂直切割\n",
    "                for x in range(1, j):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][x] + dp[i][j-x])\n",
    "        \n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        for h, w, p in prices:\n",
    "            dp[h][w] = p\n",
    "        for h in range(1, m + 1):\n",
    "            for w in range(1, n + 1):\n",
    "                mx = dp[h][w]\n",
    "                for h2 in range(1, h // 2 + 1):\n",
    "                    mx = max(mx, dp[h2][w] + dp[h-h2][w])\n",
    "                for w2 in range(1, w // 2 + 1):\n",
    "                    mx = max(mx, dp[h][w2] + dp[h][w-w2])\n",
    "                dp[h][w] = mx\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        priceMap = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for h, w, p in prices:\n",
    "            priceMap[h][w] = p\n",
    "        res = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for h in range(1, m+1):\n",
    "            resRow = res[h]\n",
    "            for w in range(1, n+1):\n",
    "                resRow[w] = max(chain(\n",
    "                    (resRow[k] + resRow[w-k] for k in range(1, w)), \n",
    "                    (res[k][w]+res[h-k][w] for k in range(1, h)),\n",
    "                    [priceMap[h][w]]\n",
    "                ))\n",
    "        return res[m][n]\n",
    "\n",
    "\n",
    "        # res[m][n] = max(res[k][n] + res[m-k][n], res[m][k]+res[m][n-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        p = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for x, y, z in prices:\n",
    "            p[x][y] = z\n",
    "\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = p[i][j]\n",
    "                for k in range(0, i + 1):\n",
    "                    f[i][j] = max(f[k][j] + f[i - k][j], f[i][j])\n",
    "                for k in range(0, j + 1):\n",
    "                    f[i][j] = max(f[i][k] + f[i][j - k], f[i][j])\n",
    "\n",
    "        return f[m][n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for h,w,p in prices:\n",
    "            dp[h][w]=p\n",
    "        \n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                for k in range(1,j):\n",
    "                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[i][j-k])\n",
    "                for l in range(1,i):\n",
    "                    dp[i][j]=max(dp[i][j],dp[l][j]+dp[i-l][j])\n",
    "\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for h,w,p in prices:\n",
    "            dp[h][w]=p\n",
    "        \n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                for k in range(1,j+1):\n",
    "                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[i][j-k])\n",
    "                for l in range(1,i+1):\n",
    "                    dp[i][j]=max(dp[i][j],dp[l][j]+dp[i-l][j])\n",
    "\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        d = {(h, w): p for h, w, p in prices}\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = max(d.get((i, j), 0), \n",
    "                max((dp[i][k] + dp[i][j - k] for k in range(1, j)), default=0),\n",
    "                max((dp[k][j] + dp[i - k][j] for k in range(1, i)), default=0))\n",
    "\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # 1. 递归\n",
    "        # value = dict()\n",
    "        # @cache\n",
    "        # def dfs(x:int, y:int)-> int:\n",
    "        #     ret = value.get((x, y), 0)\n",
    "        #     if x > 1:\n",
    "        #         for i in range(1, x):\n",
    "        #             ret = max(ret, dfs(i, y) + dfs(x - i, y))\n",
    "        #     if y > 1:\n",
    "        #         for j in range(1, y):\n",
    "        #             ret = max(ret, dfs(x, j) + dfs(x, y - j))\n",
    "        #     return ret\n",
    "        # for (h, w, price) in prices:\n",
    "        #     value[(h, w)] = price\n",
    "        # ans = dfs(m, n)\n",
    "        # dfs.cache_clear()\n",
    "        # return ans\n",
    "\n",
    "        # 2. 迭代\n",
    "        pr = {(h, w): p for h, w, p in prices}\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(pr.get((i, j), 0),\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i)), default=0))  # 水平切割\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        pr = {(h, w): p for h, w, p in prices}\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(pr.get((i, j), 0),\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i)), default=0))  # 水平切割\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        price_dict = {(price[0], price[1]): price[2] for price in prices}\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if (i, j) in price_dict:\n",
    "                    dp[i][j] = max(dp[i][j], price_dict[(i, j)])\n",
    "                for k in range(1, i//2+1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i-k][j])\n",
    "                for k in range(1, j//2+1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j-k])\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        pr = {(h, w): p for h, w, p in prices}\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # 钢条切割的二维版本\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(pr.get((i, j), 0),\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i)), default=0))  # 水平切割\n",
    "        return f[m][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        pr = {(h, w): p for h, w, p in prices}\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = max(pr.get((i, j), 0),\n",
    "                              max((f[i][k] + f[i][j - k] for k in range(1, j)), default=0),  # 垂直切割\n",
    "                              max((f[k][j] + f[i - k][j] for k in range(1, i)), default=0))  # 水平切割\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        rec = {(h,w):p for h,w,p in prices}\n",
    "        f = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                f[i][j] = rec.get((i,j), 0)\n",
    "                # 横切\n",
    "                for k in range(1,m):\n",
    "                    f[i][j] = max(f[i][j], f[k][j] + f[i-k][j])\n",
    "                # 竖切\n",
    "                for k in range(1,n):\n",
    "                    f[i][j] = max(f[i][j], f[i][k] + f[i][j-k])\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        price_dict = {(h, w): p for h,w,p in prices }\n",
    "        f = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                f[i][j] = max([price_dict.get((i,j), 0),\n",
    "                            max((f[i][k]+f[i][j-k] for k in range(1, j)), default=0),\n",
    "                            max((f[k][j]+f[i-k][j] for k in range(1, i)), default=0)\n",
    "                                ])\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        \n",
    "        l = len(prices)\n",
    "        F = [[0] * (n+1) for i in range(m+1)]\n",
    "        D = {}\n",
    "        for a,b,v in prices:\n",
    "            D[(a,b)] = v\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if (i,j) in D:F[i][j] = max(F[i][j],D[(i,j)])\n",
    "                for a in range(1,i//2+1):\n",
    "                    F[i][j] = max(F[i][j],F[a][j] + F[i-a][j])\n",
    "                for b in range(1,j//2+1):\n",
    "                    F[i][j] = max(F[i][j],F[i][b] + F[i][j-b])\n",
    "        return F[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        Row, Col = m, n\n",
    "\n",
    "        hw_p = collections.defaultdict(int)\n",
    "        for h, w, p in prices:\n",
    "            hw_p[(h, w)] = p\n",
    "\n",
    "        dp = [[0] * (Col + 1) for _ in range(Row + 1)]\n",
    "        for h in range(1, Row + 1):\n",
    "            for w in range(1, Col + 1):\n",
    "                dp[h][w] = hw_p[(h, w)]\n",
    "                for hi in range(1, h // 2 + 1):\n",
    "                    dp[h][w] = max(dp[h][w], dp[hi][w] + dp[h - hi][w])\n",
    "                for wi in range(1, w // 2 + 1):\n",
    "                    dp[h][w] = max(dp[h][w], dp[h][wi] + dp[h][w - wi])\n",
    "        \n",
    "        return dp[Row][Col]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dp = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        # 将价格信息保存为一个字典，方便查找\n",
    "        price_dict = {(h, w): p for h, w, p in prices}\n",
    "\n",
    "        def helper(h, w):\n",
    "            if h <= 0 or w <= 0:\n",
    "                return 0\n",
    "            if dp[h][w] != -1:\n",
    "                return dp[h][w]\n",
    "\n",
    "            # 直接卖出该木块的价值\n",
    "            max_val = price_dict.get((h, w), 0)\n",
    "\n",
    "            # 尝试垂直切割\n",
    "            for cut_h in range(1, h):\n",
    "                max_val = max(max_val, helper(cut_h, w) + helper(h - cut_h, w))\n",
    "        \n",
    "            # 尝试水平切割\n",
    "            for cut_w in range(1, w):\n",
    "                max_val = max(max_val, helper(h, cut_w) + helper(h, w - cut_w))\n",
    "\n",
    "            dp[h][w] = max_val\n",
    "            return max_val\n",
    "\n",
    "        return helper(m, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        mark = dict()\n",
    "\n",
    "        @cache\n",
    "        def dfs(x:int, y:int)->int:\n",
    "            ret = mark.get((x, y), 0)\n",
    "            if x > 1:\n",
    "                n = x // 2 + 1\n",
    "                for i in range(1, n):\n",
    "                    ret = max(ret, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            if y > 1:\n",
    "                n = y // 2 + 1\n",
    "                for j in range(1, n):\n",
    "                    ret = max(ret, dfs(x, j) + dfs(x, y - j))\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        for (h, w, price) in prices:\n",
    "            mark[(h, w)] = price\n",
    "        \n",
    "        ans = dfs(m, n)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        value = dict()\n",
    "\n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            ret = value.get((x, y), 0)\n",
    "\n",
    "            if x > 1:\n",
    "                for i in range(1, x):\n",
    "                    ret = max(ret, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            if y > 1:\n",
    "                for j in range(1, y):\n",
    "                    ret = max(ret, dfs(x, j) + dfs(x, y - j))\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        for (h, w, price) in prices:\n",
    "            value[(h, w)] = price\n",
    "        \n",
    "        ans = dfs(m, n)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        mark = dict()\n",
    "\n",
    "        @cache\n",
    "        def dfs(x:int, y:int)->int:\n",
    "            ret = mark.get((x, y), 0)\n",
    "            if x > 1:\n",
    "                for i in range(1, x):\n",
    "                    ret = max(ret, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            if y > 1:\n",
    "                for j in range(1, y):\n",
    "                    ret = max(ret, dfs(x, j) + dfs(x, y - j))\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        for (h, w, price) in prices:\n",
    "            mark[(h, w)] = price\n",
    "        \n",
    "        ans = dfs(m, n)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for h, w, p in prices:\n",
    "            dic[h, w] = p\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = dic[x, y]\n",
    "            for i in range(1, x):\n",
    "                res = max(res, dfs(i, y) + dfs(x - i, y))\n",
    "            for j in range(1, y):\n",
    "                res = max(res, dfs(x, j) + dfs(x, y - j))\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(m, n)\n",
    "        del dfs\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for h, w, p in prices:\n",
    "            dic[h, w] = p\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = dic[x, y]\n",
    "            for i in range(1, x):\n",
    "                res = max(res, dfs(i, y) + dfs(x - i, y))\n",
    "            for j in range(1, y):\n",
    "                res = max(res, dfs(x, j) + dfs(x, y - j))\n",
    "\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(m, n)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        mark = dict()\n",
    "\n",
    "        @cache\n",
    "        def dfs(x:int, y:int)->int:\n",
    "            ret = mark.get((x, y), 0)\n",
    "            if x > 1:\n",
    "                for i in range(1, x):\n",
    "                    ret = max(ret, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            if y > 1:\n",
    "                for j in range(1, y):\n",
    "                    ret = max(ret, dfs(x, j) + dfs(x, y - j))\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        for (h, w, price) in prices:\n",
    "            mark[(h, w)] = price\n",
    "        \n",
    "        ans = dfs(m, n)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        hash = dict()\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y) -> int:\n",
    "            if (x, y) in hash.keys():\n",
    "                ret = hash[(x, y)]\n",
    "            else: ret = 0\n",
    "\n",
    "            for i in range(1, x):\n",
    "                ret = max(ret, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            for i in range(1, y):\n",
    "                ret = max(ret, dfs(x, i) + dfs(x, y - i))\n",
    "            \n",
    "            return ret\n",
    "\n",
    "\n",
    "        for (h, w, p) in prices:\n",
    "            hash[(h, w)] = p\n",
    "        return dfs(m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, p: List[List[int]]) -> int:\n",
    "        h={(i,j):k for i,j,k in p}\n",
    "        @cache\n",
    "        def dfs(m,n):\n",
    "            if m==0 or n==0:\n",
    "                return 0\n",
    "            ans=0\n",
    "            if (m,n) in h:\n",
    "                ans=max(ans,h[(m,n)])\n",
    "            for i in range(1,m):\n",
    "                ans=max(ans,dfs(i,n)+dfs(m-i,n))\n",
    "            for j in range(1,n):\n",
    "                ans=max(ans,dfs(m,j)+dfs(m,n-j))\n",
    "            return ans\n",
    "        return dfs(m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        mp = {(h, w) : v for h, w, v in prices}\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            res = mp.get((x, y), 0)\n",
    "            if x > 1:\n",
    "                for i in range(1, x):\n",
    "                    res = max(res, dfs(i, y) + dfs(x - i, y))\n",
    "            if y > 1:\n",
    "                for j in range(1, y):\n",
    "                    res = max(res, dfs(x, j) + dfs(x, y - j))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(m, n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        values={}\n",
    "        @cache\n",
    "        def check(x,y):\n",
    "            if (x,y) in values:\n",
    "                ret=values[(x,y)]\n",
    "            else:\n",
    "                ret=0\n",
    "            if x>1:\n",
    "                for i in range(1,x):\n",
    "                    ret=max(ret,check(x-i,y)+check(i,y))\n",
    "            if y>1:\n",
    "                for i in range(1,y):\n",
    "                    ret=max(ret,check(x,y-i)+check(x,i))\n",
    "            return ret\n",
    "        check.cache_clear()\n",
    "        for x,y,z in prices:\n",
    "            values[(x,y)]=z\n",
    "        return check(m,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        hash = dict()\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if (x, y) in hash.keys():\n",
    "                ret = hash[(x, y)]\n",
    "            else: ret = 0\n",
    "\n",
    "            for i in range(1, x):\n",
    "                ret = max(ret, dfs(i, y) + dfs(x - i, y))\n",
    "\n",
    "            for i in range(1, y):\n",
    "                ret = max(ret, dfs(x, i) + dfs(x, y - i))\n",
    "            \n",
    "            return ret\n",
    "\n",
    "        for (h, w, p) in prices:\n",
    "            hash[(h, w)]=p\n",
    "        return dfs(m, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for x, y, p in prices:\n",
    "            d[(x, y)] = p\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            res = d.get((i, j), 0)\n",
    "            for r in range(1, i // 2 + 1):\n",
    "                res = max(res, f(r, j) + f(i - r, j))\n",
    "            for c in range(1, j // 2 + 1):\n",
    "                res = max(res, f(i, c) + f(i, j - c))\n",
    "            return res\n",
    "\n",
    "        return f(m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        # 只能横切和竖切\n",
    "        # first method：dp\n",
    "        # m, n = m + 1, n + 1\n",
    "        # dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        # for pri in prices:\n",
    "        #     dp[pri[0]][pri[1]] = pri[2]\n",
    "        # for i in range(1, m):\n",
    "        #     for j in range(1, n):\n",
    "        #         for k in range(1, i):\n",
    "        #             dp[i][j] = max(dp[i][j], dp[i - k][j] + dp[k][j])\n",
    "        #         for k in range(1, j):\n",
    "        #             dp[i][j] = max(dp[i][j], dp[i][j - k] + dp[i][k])\n",
    "        # return dp[-1][-1]\n",
    "\n",
    "        # second method: dfs\n",
    "        values = dict()\n",
    "        for a, b , c in prices:\n",
    "            values[(a, b)] = c\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            ans = values.get((x, y), 0)\n",
    "            if x > 1:\n",
    "                for i in range(1, x):\n",
    "                    ans = max(ans, dfs(i, y) + dfs(x - i, y))\n",
    "            if y > 1:\n",
    "                for i in range(1, y):\n",
    "                    ans = max(ans, dfs(x, i) + dfs(x, y - i))\n",
    "            return ans\n",
    "        return dfs(m, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:\n",
    "        d_price = {}\n",
    "        for each in prices:\n",
    "            d_price[(each[0], each[1])] = each[2]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            res = d_price.get((x, y), 0)\n",
    "            if x > 1:\n",
    "                for i in range(1, x):\n",
    "                    res = max(res, dfs(i, y) + dfs(x-i, y))\n",
    "            if y > 1:\n",
    "                for i in range(1, y):\n",
    "                    res = max(res, dfs(x, i) + dfs(x, y-i))\n",
    "            return res\n",
    "        res = dfs(m, n)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
